package DataStructure;


import DataStructure.math.Maths;

//哈希表
public class HashTable<K extends Comparable<K>,V>{
    private Node<K,V>[] table;
    private int p=2;
    private int size;

    private static class Node<K extends Comparable<K>,V>{
        private final K key;
        private V value;
        private Node<K,V> next;
        public Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    public HashTable(int num) {
        table=new Node[num];
        for (int i = 0; i < num; i++) {
            table[i]=new Node<>(null,null,null);
        }
        //查找最近质数
        for (int i = num%2==0?num-1:num;i>=2;i-=2) {
            if(Maths.isPrime(i)){
                p=i;
                break;
            }
        }
    }
    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    //fix
    public void add(K key, V value){
        int pos=hash(key);
        table[pos].next=new Node<>(key,value,table[pos].next);
        size++;
    }

    public V remove(K key){
        int pos=hash(key);
        Node<K,V> n=table[pos];
        size--;
        while(n.next!=null){
            if(n.next.key==key){
                Node<K,V> tmp=n.next;
                n.next=tmp.next;
                return tmp.value;
            }
            n=n.next;
        }
        return null;
    }

    public boolean contains(K key){
        return get(key)!=null;
    }

    public V get(K key){
        int pos=hash(key);
        Node<K,V> n=table[pos].next;
        while(n!=null){
            if(n.key==key)
                return n.value;
            n=n.next;
        }
        return null;
    }

    private int hash(K key){
        return key.hashCode();
    }

}
